package done.easy_501_600;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 538. Convert BST to Greater Tree 把二叉搜索树转换为累加树
 * <p>
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树
 * （Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它
 * 的节点值之和。
 * <p>
 * 例如：
 * 输入: 二叉搜索树:
 * 5
 * /   \
 * 2     13
 * <p>
 * 输出: 转换为累加树:
 * 18
 * /   \
 * 20     13
 *
 * @author 大硕
 * 2019-04-13 8:13 AM
 **/
@SuppressWarnings("all")
public class ConvertBSTToGreaterTree {

    //递归写法
    public TreeNode convertBST(TreeNode root) {
        // 190413 first
        return null;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(5, 2, 13);
        info(convertBST(root));
    }
}














































/*
// NO.1 递归写法
public int preNum = 0;

//递归写法
public TreeNode convertBST(TreeNode root) {
    unPreOrder(root);
    return root;
}

public void unPreOrder(TreeNode root){
    if(root == null)
        return;
    unPreOrder(root.right);
    root.val += preNum;
    preNum = root.val;
    unPreOrder(root.left);
}
*/

// NO.2 非递归写法
/*public TreeNode convertBST(TreeNode root) {
    if(root == null)
        return root;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    //stack.add(root);
    TreeNode node = root;
    while(node != null || !stack.isEmpty()){
        while(node != null){
            stack.add(node);
            node = node.right;
        }
        node = stack.pop();
        node.val += preNum;
        preNum = node.val;
        if(node.left != null)
            node = node.left;
        else
            node = null;
    }
    return root;
}*/
